//给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。 
//
// 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0
//] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取
//时，游戏结束。 
//
// 如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分
//数最大化。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,5,2]
//输出：false
//解释：一开始，玩家 1 可以从 1 和 2 中进行选择。
//如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）
//可选。 
//所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
//因此，玩家 1 永远不会成为赢家，返回 false 。 
//
// 示例 2： 
//
// 
//输入：nums = [1,5,233,7]
//输出：true
//解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
//最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 10⁷ 
// 
// Related Topics递归 | 数组 | 数学 | 动态规划 | 博弈 
//
// 👍 567, 👎 0 
//
//
//
//

package leetcode.editor.cn;

class PredictTheWinner {
    public static void main(String[] args) {
        Solution solution = new PredictTheWinner().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        class Pair {
            // fir：先手选择
            // sec：后手选择
            int fir, sec;

            public Pair(int fir, int sec) {
                this.fir = fir;
                this.sec = sec;
            }
        }

        // 参照labuladong：https://labuladong.gitee.io/algo/3/28/93/
        public boolean PredictTheWinner(int[] nums) {
            int n = nums.length;
            // 表示在[i,j]的区间，先选和后选的最大值
            Pair[][] dp = new Pair[n][n];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    dp[i][j] = new Pair(0, 0);

            // i == j时，先手只有一个选择，后手没有选择
            for (int i = 0; i < n; i++) dp[i][i].fir = nums[i];

            // 倒序遍历
            for (int i = n - 2; i >= 0; i--) {
                for (int j = i + 1; j < n; j++) {
                    // 先手选择左边，那么还剩右边，而且变成了后手
                    int left = nums[i] + dp[i + 1][j].sec;
                    // 选右边相反
                    int right = nums[j] + dp[i][j - 1].sec;

                    // 套用状态转移方程
                    // 先手肯定会选择更大的结果，后手的选择随之改变
                    // 先手选最大的
                    if (left > right) {
                        dp[i][j].fir = left;
                        dp[i][j].sec = dp[i + 1][j].fir;
                    } else {
                        dp[i][j].fir = right;
                        dp[i][j].sec = dp[i][j - 1].fir;
                    }
                }
            }

            // 求差值
            Pair pair = dp[0][n - 1];
            return (pair.fir - pair.sec) >= 0 ? true : false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
